{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Newton's method in $n$ dimensions"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "import numpy as np\n",
        "import numpy.linalg as la"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "def f(xvec):\n",
        "    x, y = xvec\n",
        "    return np.array([\n",
        "        x + 2*y -2,\n",
        "        x**2 + 4*y**2 - 4\n",
        "        ])\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {},
      "outputs": [],
      "source": [
        "def Jf(xvec):\n",
        "    x, y = xvec\n",
        "    return np.array([\n",
        "        [1, 2],\n",
        "        [2*x, 8*y]\n",
        "        ])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Pick an initial guess."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "x = np.array([1, 2])"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Now implement Newton's method."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[-0.83333333  1.41666667]\n"
          ]
        }
      ],
      "source": [
        "x = x - la.solve(Jf(x), f(x))\n",
        "print(x)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "Check if that's really a solution:"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "data": {
            "text/plain": [
              "array([0.        , 4.72222222])"
            ]
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "f(x)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "* What's the cost of one iteration?\n",
        "* Is there still something like quadratic convergence?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "--------------------\n",
        "Let's keep an error history and check."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {
        "collapsed": false
      },
      "outputs": [],
      "source": [
        "xtrue = np.array([0, 1])\n",
        "errors = []\n",
        "x = np.array([1, 2])"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 19,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "[1.50295992e-16 1.00000000e+00]\n"
          ]
        }
      ],
      "source": [
        "x = x - la.solve(Jf(x), f(x))\n",
        "errors.append(la.norm(x-xtrue))\n",
        "print(x)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 20,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.931694990624912\n",
            "0.21174886150566186\n",
            "0.016858985788667225\n",
            "0.0001252212359224592\n",
            "7.011683691522178e-09\n",
            "1.5029599174076677e-16\n",
            "1.5029599174076677e-16\n",
            "1.5029599174076677e-16\n",
            "1.5029599174076677e-16\n",
            "1.5029599174076677e-16\n"
          ]
        }
      ],
      "source": [
        "for e in errors:\n",
        "    print(e)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 21,
      "metadata": {
        "collapsed": false
      },
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "0.24393468845452265\n",
            "0.37600123952862446\n",
            "0.4405701781738273\n",
            "0.4471634974555712\n",
            "3.0570515787795163\n",
            "6653537385912580.0\n",
            "6653537385912580.0\n",
            "6653537385912580.0\n",
            "6653537385912580.0\n"
          ]
        }
      ],
      "source": [
        "for i in range(len(errors)-1):\n",
        "    print(errors[i+1]/errors[i]**2)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.7.2+"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 2
}